<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Symmetries
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial084.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial079.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc158">11.6</A>&nbsp;&nbsp;Symmetries</H2>
Consider the following puzzle, where numbers from 1 to 19 have to be arranged
in a hexagonal shape such that every diagonal sums up to 38:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
puzzle(Pattern) :-
        Pattern = [
                   A,B,C,
                  D,E,F,G,
                 H,I,J,K,L,
                  M,N,O,P,
                   Q,R,S
                  ],
        Pattern :: 1 .. 19,

        % Problem constraints
        alldifferent(Pattern),
          A+B+C #= 38,     A+D+H #= 38,     H+M+Q #= 38,
         D+E+F+G #= 38,   B+E+I+M #= 38,   D+I+N+R #= 38,
        H+I+J+K+L #= 38, C+F+J+N+Q #= 38, A+E+J+O+S #= 38,
         M+N+O+P #= 38,   G+K+O+R #= 38,   B+F+K+P #= 38,
          Q+R+S #= 38,     L+P+S #= 38,     C+G+L #= 38,
        ...
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
In this formulation, the problem has 12 solutions, but it turns out they
are just rotated and mirrored variants of each other.
Removal of symmetries is still an area of active research, but a simple
method is applicable in situations like this one.
One can add constraints which require the solution to have certain
additional properties, and so exclude many of the symmetric solutions:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
        ...,
        % Optional anti-symmetry constraints
        % Forbid rotated solutions: require A to be the smallest corner
        A #&lt; C, A #&lt; H, A #&lt; L, A #&lt; S, A #&lt; Q,
        % Forbid solutions mirrored on the A-S diagonal
        C #&lt; H.
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<HR>
<A HREF="tutorial084.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial079.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
</BODY>
</HTML>
